package bit_operation;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-04-15 16:19
 */
public class II003_countBits {
    // 法1: 暴力法
    // 遍历每个数字,通过 除法,取模 累计1的个数,最终返回结果
    // 时间复杂度: O(n*每个数字的位数)

    // 法2: dp
    // 偶数1的个数 = 除2后的那个数)
    // 奇数1的个数 = 前一个偶数的1的个数+1)
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0) {
                // 偶数 (1的个数 = 除2后的那个数)
                ans[i] = ans[i / 2];
            } else {
                // 奇数 (1的个数 = 前一个偶数的1的个数+1)
                ans[i] = ans[i - 1] + 1;
            }
        }
        return ans;
    }
}
